//680 验证回文字符串 Ⅱ
/*
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串

输入: "aba"
输出: True

输入: "abca"
输出: True
解释: 你可以删除c字符



*/
class Solution
{
public:
	bool checkPalindrome(const string &s, int low, int high)
	{
		for (int i = low, j = high; i < j; ++i, --j)
		{
			if (s[i] != s[j])
			{
				return false;
			}
		}
		return true;
	}

	bool validPalindrome(string s)
	{
		int low = 0, high = s.size() - 1;
		while (low < high)
		{
			char c1 = s[low], c2 = s[high];
			if (c1 == c2) //直接将 low 和 high 进行比较，如果则是回文
			{
				++low;
				--high;
			}
			else //在low方或high方随意有一方跳过一个元素可以造成回文则成功
			{
				return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high);
			}
		}
		return true;
	}
};